1. Field of the Invention
The present invention relates to networks and network topologies. More particularly, the present invention relates to a network and a network protocol, referred to herein as the “virtual root bridge (VRBP) protocol,” that can support redundant links between two or more network clusters or instances of the network.
2. Background Information
A multipoint-to-multipoint (“M2M”) network is an alternative architecture that can trade off lower performance for lower cost as compared to, for example, the point-to-point (“P2P”) architecture that can used in networks. As compared to a P2P network, a M2M network includes characteristics such as, for example, the following: links are not pre-configured; links are dynamic rather than static; and links are less reliable. Due to such characteristics, the best choice of path through the M2M network may change more often. Additionally, it is possible that portions of the network can become, for a time, isolated from the rest of the network. Furthermore, the cluster size (i.e., the number of nodes with M2M links to other nodes in the cluster) is inherently limited to approximately eight nodes. The M2M architecture can support various types of network topologies, such as, for example, wireless mesh networks.
FIG. 1 is a diagram illustrating an ad hoc wireless mesh network 100 in which the client devices 105 form the mesh. An ad hoc mesh network is a wireless mesh network created when multiple wireless client devices 105 each act as a router (either at Layer 2 or at Layer 3) to transport traffic destined to or from another wireless client device 105. In such a network, there are no access points (APs) and no hierarchy. There may or may not be a connection to an external network. It should be noted that conventional mesh network topologies generally assumes there is no such connection to an external network, even though such a network may be of limited usefulness.
FIG. 2 is a diagram illustrating an infrastructure mesh network 200 that includes APs 205 and client devices 210, and communicates with external networks using a network connection node 215. Infrastructure mesh networks comprise APs (“nodes”) 205 that are interconnected wirelessly. The wireless connections generally use the same radios used to connect to the client devices 210. Infrastructure mesh networks are somewhat hierarchical in that a mesh cluster—a group of nodes 205 connected sharing a mesh—is connected to an upstream network (e.g., via network connection node 215) that may be itself a mesh cluster. Infrastructure mesh networks are generally more static than ad hoc mesh networks, and the client devices 205 do not participate in the mesh. Ideally, the client devices 205 use the same configuration as would be used to connect to a conventional wireless network. In contrast, any client in an ad hoc mesh network runs special mesh networking software.
To select paths through the network for purposes of, for example, communicating data and passing data traffic, the Rapid Spanning Tree Protocol (RSTP) can be used. RSTP is described in the I.E.E.E. 802.1w standard, the entire contents of which is incorporated by reference herein. RSTP is an evolution of the Spanning Tree Protocol (“STP,” described in the I.E.E.E. 802.1D-1998 standard, the entire contents of which is incorporated by reference herein) and provides for a faster spanning tree convergence after a topology change. In other words, RSTP is an I.E.E.E.-standard protocol that dynamically disables links in an Ethernet LAN to create a loop-free spanning tree (i.e., a collection of links that provide connectivity between any pair of nodes in the tree) that uses normal bridge forwarding. Any network using bridge forwarding cannot have active loops, because broadcast and multicast frames can circulate substantially forever around such a loop. RSTP works by selectively disabling links to create a loop-free spanning tree (i.e., a collection of links that provide connectivity between any pair of nodes in the tree).
One factor limiting the size of an RSTP network is the aging of root bridge information. There is a limit on the maximum number of hops between the RSTP root bridge and any other bridge within that RSTP network. The root bridge can be determined by which bridge has the numerically lowest bridge priority value. In case of a tie, the bridge with the numerically lowest MAC address can be selected. Information on the root bridge expires after a period of time defined by the MaxAge parameter. Under normal operation, the information propagates one hop every HelloTime interval. In other words, any information on the root bridge that is older than the MaxAge parameter must be discarded. Root-bridge information is propagated in Bridge Protocol Data Units (BPDUs) that are generally sent every HelloTime seconds. The resulting limit on the network diameter is given by Equation (1):
                    MaxHops        ≤                              MaxAge            HelloTime                    -          1.                                    (        1        )            For example, for (default) values of HelloTime=2 seconds and MaxAge=20 seconds, MaxHops≦9. Such a limit is observed for any reasonable combination of link and node failures. The I.E.E.E. recommended hop limit for the base network (i.e., a network with no link or node failure) is seven. However, a wireless mesh network can require a lower hop limit, because the links are inherently less reliable than conventional wired links.
With MaxHops≦9, such a result generally means that there can be no more than nine hops from any one node to any other node. The root bridge and backup root bridge should be located near the center of the network topology, so that no node is normally more than approximately five hops away from the root bridge. With conventional network topologies, the maximum number of hops should not exceed such a limit even if one or two links fail, or the root bridge fails. (With a loop topology, the number of nodes in the loop, plus the number of hops to the root bridge if it is not in the loop, must not exceed nine.) The exact constraint on mesh network size depends on such factors as, for example the topology and how reliable the network needs to be. In other words, there is an interaction between the desired network reliability and the maximum network size. If the network is required to be extremely reliable, then it becomes necessary to allow for more unlikely failure scenarios where multiple links or nodes fail simultaneously. Such a scenario implies that the hop limit for the base network would be lower, which can severely limit the maximum allowable network size. In sum, conventional RSTP is not a complete solution for determining paths through a large mesh network, because of scalability limits.
Some mesh networking algorithms can be used to partition a hierarchical network in order to overcome scaling limitations of the algorithm. For example, the Ad-hoc On-demand Distance Vector (“AODV”) protocol could be run within each sector of the network, while a separate instance of AODV could be used to provide forwarding in the rest of the aggregation network. However, RSTP does not easily support such a type of partitioning. If there are redundant links between RSTP instances, then loops will exist that will not be detected by RSTP.
Therefore, there is a need for a network topology and networking protocol than can support scalability and partitioning in networks, such as, for example, mesh networks and the like, that use path selection algorithms such as, for example, RSTP or the like.